<h2>Problem 122</h2>
<div style="color:#666;font-size:80%;">02 June 2006</div><br />
<div class="problem_content">
<p>The most naive way of computing <i>n</i><img src="" style="display:none;" alt="^(" /><sup>15</sup><img src="" style="display:none;" alt=")" /> requires fourteen multiplications:</p>
<p style='margin-left:100px;'><i>n</i> <img src='images/symbol_times.gif' width='9' height='9' alt='&times;' border='0' style='vertical-align:middle;' /> <i>n</i> <img src='images/symbol_times.gif' width='9' height='9' alt='&times;' border='0' style='vertical-align:middle;' /> ... <img src='images/symbol_times.gif' width='9' height='9' alt='&times;' border='0' style='vertical-align:middle;' /> <i>n</i> = <i>n</i><img src="" style="display:none;" alt="^(" /><sup>15</sup><img src="" style="display:none;" alt=")" /></p>
<p>But using a &quot;binary&quot; method you can compute it in six multiplications:</p>
<p style='margin-left:100px;'><i>n</i> <img src='images/symbol_times.gif' width='9' height='9' alt='&times;' border='0' style='vertical-align:middle;' /> <i>n</i> = <i>n</i><img src="" style="display:none;" alt="^(" /><sup>2</sup><img src="" style="display:none;" alt=")" /><br />
<i>n</i><img src="" style="display:none;" alt="^(" /><sup>2</sup><img src="" style="display:none;" alt=")" /> <img src='images/symbol_times.gif' width='9' height='9' alt='&times;' border='0' style='vertical-align:middle;' /> <i>n</i><img src="" style="display:none;" alt="^(" /><sup>2</sup><img src="" style="display:none;" alt=")" /> = <i>n</i><img src="" style="display:none;" alt="^(" /><sup>4</sup><img src="" style="display:none;" alt=")" /><br />
<i>n</i><img src="" style="display:none;" alt="^(" /><sup>4</sup><img src="" style="display:none;" alt=")" /> <img src='images/symbol_times.gif' width='9' height='9' alt='&times;' border='0' style='vertical-align:middle;' /> <i>n</i><img src="" style="display:none;" alt="^(" /><sup>4</sup><img src="" style="display:none;" alt=")" /> = <i>n</i><img src="" style="display:none;" alt="^(" /><sup>8</sup><img src="" style="display:none;" alt=")" /><br />
<i>n</i><img src="" style="display:none;" alt="^(" /><sup>8</sup><img src="" style="display:none;" alt=")" /> <img src='images/symbol_times.gif' width='9' height='9' alt='&times;' border='0' style='vertical-align:middle;' /> <i>n</i><img src="" style="display:none;" alt="^(" /><sup>4</sup><img src="" style="display:none;" alt=")" /> = <i>n</i><img src="" style="display:none;" alt="^(" /><sup>12</sup><img src="" style="display:none;" alt=")" /><br />
<i>n</i><img src="" style="display:none;" alt="^(" /><sup>12</sup><img src="" style="display:none;" alt=")" /> <img src='images/symbol_times.gif' width='9' height='9' alt='&times;' border='0' style='vertical-align:middle;' /> <i>n</i><img src="" style="display:none;" alt="^(" /><sup>2</sup><img src="" style="display:none;" alt=")" /> = <i>n</i><img src="" style="display:none;" alt="^(" /><sup>14</sup><img src="" style="display:none;" alt=")" /><br />
<i>n</i><img src="" style="display:none;" alt="^(" /><sup>14</sup><img src="" style="display:none;" alt=")" /> <img src='images/symbol_times.gif' width='9' height='9' alt='&times;' border='0' style='vertical-align:middle;' /> <i>n</i> = <i>n</i><img src="" style="display:none;" alt="^(" /><sup>15</sup><img src="" style="display:none;" alt=")" /></p>
<p>However it is yet possible to compute it in only five multiplications:</p>
<p style='margin-left:100px;'><i>n</i> <img src='images/symbol_times.gif' width='9' height='9' alt='&times;' border='0' style='vertical-align:middle;' /> <i>n</i> = <i>n</i><img src="" style="display:none;" alt="^(" /><sup>2</sup><img src="" style="display:none;" alt=")" /><br />
<i>n</i><img src="" style="display:none;" alt="^(" /><sup>2</sup><img src="" style="display:none;" alt=")" /> <img src='images/symbol_times.gif' width='9' height='9' alt='&times;' border='0' style='vertical-align:middle;' /> <i>n</i> = <i>n</i><img src="" style="display:none;" alt="^(" /><sup>3</sup><img src="" style="display:none;" alt=")" /><br />
<i>n</i><img src="" style="display:none;" alt="^(" /><sup>3</sup><img src="" style="display:none;" alt=")" /> <img src='images/symbol_times.gif' width='9' height='9' alt='&times;' border='0' style='vertical-align:middle;' /> <i>n</i><img src="" style="display:none;" alt="^(" /><sup>3</sup><img src="" style="display:none;" alt=")" /> = <i>n</i><img src="" style="display:none;" alt="^(" /><sup>6</sup><img src="" style="display:none;" alt=")" /><br />
<i>n</i><img src="" style="display:none;" alt="^(" /><sup>6</sup><img src="" style="display:none;" alt=")" /> <img src='images/symbol_times.gif' width='9' height='9' alt='&times;' border='0' style='vertical-align:middle;' /> <i>n</i><img src="" style="display:none;" alt="^(" /><sup>6</sup><img src="" style="display:none;" alt=")" /> = <i>n</i><img src="" style="display:none;" alt="^(" /><sup>12</sup><img src="" style="display:none;" alt=")" /><br />
<i>n</i><img src="" style="display:none;" alt="^(" /><sup>12</sup><img src="" style="display:none;" alt=")" /> <img src='images/symbol_times.gif' width='9' height='9' alt='&times;' border='0' style='vertical-align:middle;' /> <i>n</i><img src="" style="display:none;" alt="^(" /><sup>3</sup><img src="" style="display:none;" alt=")" /> = <i>n</i><img src="" style="display:none;" alt="^(" /><sup>15</sup><img src="" style="display:none;" alt=")" /></p>
<p>We shall define m(<i>k</i>) to be the minimum number of multiplications to compute <i>n</i><img src="" style="display:none;" alt="^(" /><sup><i>k</i></sup><img src="" style="display:none;" alt=")" />; for example m(15) = 5.</p>
<p>For 1 <img src='images/symbol_le.gif' width='10' height='12' alt='&le;' border='0' style='vertical-align:middle;' /> <i>k</i> <img src='images/symbol_le.gif' width='10' height='12' alt='&le;' border='0' style='vertical-align:middle;' /> 200, find <span style='font-family:times new roman;font-size:13pt;'><img src='images/symbol_sum.gif' width='11' height='14' alt='&sum;' border='0' style='vertical-align:middle;' /></span> m(<i>k</i>).</p>

</div><br />
